package com.sakura.二分查找;

import java.util.Arrays;

// 定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。
//
//例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
//
//现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
//
//请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。
public class Code04_比较字符串最小字母出现频次 {

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] wordsPre = new int[words.length]; // 前导数
        for (int i = 0; i < words.length; i++) {
            wordsPre[i] = f(words[i]);
        }
        // 排序
        Arrays.sort(wordsPre);
        int[] ans = new int[queries.length];
        for (int i = 0; i < ans.length; i++) {
            // 二分
            ans[i] = wordsPre.length - lowerBound(wordsPre, f(queries[i]));
        }

        return ans;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private int f(String word) {
        int cnt = 0;
        char ch = 'z';
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c < ch) {
                ch = c;
                cnt = 1;
            } else if (c == ch) {
                cnt++;
            }
        }
        return cnt;
    }
}
